package basic;

public class sort {

    /**
     * 冒泡排序
     * 时间: O(n^2), O(n)~O(n^2); 空间: O(1); 稳定
     * @param array
     * @return
     */
    private static int[] bubble(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int tmp = 0;
        for (int i = array.length; i >= 0; i--) {
            for (int j = 0; j < i-1; j++) {
                if (array[j+1] < array[j]) {
                    tmp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = tmp;
                }
            }
        }
        return array;
    }


    /**
     * 选择排序
     * 时间: O(n^2), O(n^2)~O(n^2); 空间: O(1); 不稳定
     * @param array
     * @return
     */
    private static int[] selection(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int tmp = 0;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;
        }
        return array;
    }

    /**
     * 插入排序
     * 时间: O(n^2), O(n)~O(n^2); 空间: O(1); 稳定
     * @param array
     * @return
     */
    private static int[] insert(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 1; i < array.length-1; i++) {
            int current = array[i+1];
            int pre = i;
            while (pre >=0 && current < array[pre]) {
                array[pre+1] = array[pre];
                pre--;
            }
            array[pre+1] = current;
        }
        return array;
    }


    public static void main(String[] args) {
        System.out.println("basic sort....");
        int[] arr = new int[] {4,5,3,6,2,7,1,8,9,1};
//        System.out.println("1.bubble sort....");
//        int[] arrRes = bubble(arr);
//        System.out.println("2.selection sort....");
//        int[] arrRes = selection(arr);
        System.out.println("3.insert sort....");
        int[] arrRes = insert(arr);
        System.out.print("arrRes:");
        for (int i: arrRes) {
            System.out.print(i+",");
        }
        System.out.println();
    }

}
